For convenient reference to stored computer data, the computer data is typically contained in one or more files. Each file has a logical address space for addressing the computer data in the file. In a file server, an operating system program called a file system manager assigns each file a unique numeric identifier called a “file handle,” and also maps the logical address space of the file to a storage address space of at least one data storage device such as a disk drive.
Typically a human user or an application program accesses the computer data in a file by requesting the file system manager to locate the file. After the file system manager returns an acknowledgement that the file has been located, the user or application program sends requests to the file system manager for reading data from or writing data to specified logical addresses of the file.
One of the major responsibilities of the file system manager is to manage and allocate storage space. Normally, a file will consist of a collection of extents of storage space. The extents themselves may consist of consistent sized pieces, known as file system blocks, or they may be of various size extents. Larger extents reduce the number of things that must be managed; however, larger extents may be counter-productive to file system features such as thin provisioning, block sharing, or block de-duplication. In addition, very large extents can make it costly to create small files or to use the storage space efficiently in the face of file creations and deletions. When large extents are normally used, the file system usually has mechanisms in place that allow files to be created from smaller entities, when large extents are not available (for example when the file system has aged and become fragmented).
In order to effectively support a variety of file sizes, possibly using various extent sizes, the file mapping is normally accomplished with some form of tree structure. Two commonly used tree structures are the Indirect Block Tree originally introduced in UNIX, while many newer file systems, such as Oracle's Solaris ZFS, use a form of B-tree to keep track of the extents.